<?php

/**
 * 构造hashTable和解决hash冲突
 * 哈希表不可避免冲突（collision）现象：对不同的关键字可能得到同一哈希地址，即key1≠key2，而hash(key1)=hash(key2）。
 * 具有相同函数值的关键字对该哈希函数来说称为同义词（synonym）。解决哈希冲突常用的两种方法是：开放定址法和链地址法。
 * Class HashTable
 */
class HashTable
{
    public  $table = array();
    public  $size = 10;
//    public function __construct()
//    {
//        // SplFixedArray创建的数组比一般的Array()效率更高，因为更接近C的数组。
//        // 创建时需要指定尺寸
//        $this->table = new \SplFixedArray($this->size);
//    }
    // 简单hash算法。输入key，输出hash后的整数
    private function key2Hash($key)
    {
        // key中每个字符所对应的ASCII的值
        $len = strlen($key);
        $total = 0;
        for ($i=0;$i<$len;$i++){
            $total +=ord($key[$i]);
        }
        return $total % $this->size;
    }
    // 赋值
    public function set($key, $value)
    {
        $key = $this->key2Hash($key);
        $this->table[$key] = $value;
        return true;
    }
    //取值
    public function get($key)
    {
        $key = $this->key2Hash($key);
        return $this->table[$key];

    }
    // 哈希查找
    public function hashSearch($key)
    {
        $key = $this->key2Hash($key);
        return $this->table[$key];
    }
    // 改变哈希表长度
    public function editSize($size)
    {
        $this->size = $size;
        return true;
    }
}

/**
 * 1、开放定址法
当冲突发生时，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
 * 公式为：fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)。
 * Class HashTable2
 */
class HashTable2
{
    public  $table = array();
    public  $size = 12;
//    public function __construct()
//    {
//        // SplFixedArray创建的数组比一般的Array()效率更高，因为更接近C的数组。
//        // 创建时需要指定尺寸
//        $this->table = new \SplFixedArray($this->size);
//    }
    // 简单hash算法。输入key，输出hash后的整数
    private function key2Hash($key)
    {

        return $key % $this->size;
    }
    // 赋值
    public function set($key, $value)
    {
        $key = $this->key2Hash($key);
        $i = 0;
        while ($this->table[$key] && $i<12){
            $key = $this->key2Hash($key+1);
            $i++;
        }
        $this->table[$key] = $value;
        return true;
    }
    //取值
    public function get($key)
    {
        $key = $this->key2Hash($key);
        return $this->table[$key];

    }
    // 哈希查找
    public function hashSearch($key)
    {
        $key = $this->key2Hash($key);
        return $this->table[$key];
    }
}

//测试
$ht = new HashTable2();
$keys = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34];
for ($i = 0; $i < count($keys); $i++) {
    $key = $keys[$i];
    $ht->set($key, $key);
}
echo '<pre>';
print_r($ht->table);
echo '</pre>';

